package com.cube.algorithms.heuristic;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;


/**
 * @author litb
 * @since 2025/6/18 15:47
 * <p>
 * 使用启发式算法（最近邻法）解决旅行商问题(TSP)的示例。
 * * 该示例在一个文件中包含了所有必要的类，以便于理解和运行。
 */
public class TspHeuristicExample {

    /**
     * 程序主入口，用于演示算法效果。
     *
     * @param args 命令行参数（未使用）
     */
    public static void main(String[] args) {
        // 创建一个城市列表用于测试
        List<City> cities = new ArrayList<>();
        cities.add(new City("北京", 116.46, 39.92));
        cities.add(new City("上海", 121.48, 31.22));
        cities.add(new City("广州", 113.23, 23.16));
        cities.add(new City("深圳", 114.07, 22.62));
        cities.add(new City("成都", 104.06, 30.67));
        cities.add(new City("杭州", 120.19, 30.26));
        cities.add(new City("西安", 108.95, 34.27));

        // 创建算法实例并执行
        TspHeuristicExample solver = new TspHeuristicExample();
        Tour resultTour = solver.findShortestTour(cities);

        // 打印结果
        System.out.println("最近邻启发式算法找到的路径:");
        String pathString = resultTour.getPath().stream()
                .map(City::getName)
                .collect(Collectors.joining(" -> "));
        System.out.println(pathString);
        System.out.printf("总距离: %.2f%n", resultTour.getTotalDistance());

        System.out.println("\n注意: 此解是启发式算法给出的近似最优解，不一定是全局最优解。");
    }

    /**
     * 使用最近邻启发式算法寻找一条较优的路径。
     *
     * @param cities 待访问的城市列表
     * @return 一个包含路径和总距离的Tour对象
     */
    public Tour findShortestTour(List<City> cities) {
        // 如果城市列表为空或只有一个城市，则无需计算
        if (cities == null || cities.size() <= 1) {
            return new Tour(cities, 0.0);
        }

        // 创建一个可修改的未访问城市列表
        List<City> unvisitedCities = new ArrayList<>(cities);
        // 用于存储最终路径
        List<City> tourPath = new ArrayList<>();

        // 选择第一个城市作为起点
        City startCity = unvisitedCities.remove(0);
        City currentCity = startCity;
        tourPath.add(currentCity);

        // 当仍有未访问的城市时，循环继续
        while (!unvisitedCities.isEmpty()) {
            City nearestCity = null;
            double minDistance = Double.MAX_VALUE;

            // 遍历所有未访问的城市，找到距离当前城市最近的一个
            for (City city : unvisitedCities) {
                double distance = currentCity.distanceTo(city);
                // 如果找到一个更近的城市
                if (distance < minDistance) {
                    minDistance = distance;
                    nearestCity = city;
                }
            }
            // 将找到的最近城市设置为当前城市，并更新路径
            currentCity = nearestCity;
            tourPath.add(currentCity);
            unvisitedCities.remove(currentCity);
        }

        // 路径构建完成后，计算总距离
        double totalDistance = 0.0;
        for (int i = 0; i < tourPath.size() - 1; i++) {
            totalDistance += tourPath.get(i).distanceTo(tourPath.get(i + 1));
        }
        // 添加从最后一个城市返回起点的距离，形成闭环
        totalDistance += tourPath.get(tourPath.size() - 1).distanceTo(startCity);
        // 将起点添加到路径末尾，以表示闭环
        tourPath.add(startCity);


        return new Tour(tourPath, totalDistance);
    }

    /**
     * 内部类，用于表示一个城市。
     * 包含城市的名称和二维坐标。
     */
    public static class City {
        /**
         * 城市名称
         */
        private final String name;
        /**
         * 城市的x坐标
         */
        private final double x;
        /**
         * 城市的y坐标
         */
        private final double y;

        /**
         * City的构造函数
         *
         * @param name 城市名称
         * @param x    x坐标
         * @param y    y坐标
         */
        public City(String name, double x, double y) {
            this.name = name;
            this.x = x;
            this.y = y;
        }

        /**
         * 获取城市名称
         *
         * @return 城市名称
         */
        public String getName() {
            return name;
        }

        /**
         * 计算当前城市到另一个城市的欧几里得距离
         *
         * @param other 另一个城市
         * @return 两个城市之间的距离
         */
        public double distanceTo(City other) {
            double deltaX = this.x - other.x;
            double deltaY = this.y - other.y;
            return Math.sqrt(deltaX * deltaX + deltaY * deltaY);
        }

        @Override
        public String toString() {
            return name;
        }
    }

    /**
     * 内部类，用于封装TSP问题的解。
     * 包含最终的城市访问路径和总距离。
     */
    public static class Tour {
        /**
         * 城市访问的有序列表
         */
        private final List<City> path;
        /**
         * 总旅行距离
         */
        private final double totalDistance;

        /**
         * Tour的构造函数
         *
         * @param path          旅行路径
         * @param totalDistance 总距离
         */
        public Tour(List<City> path, double totalDistance) {
            this.path = path;
            this.totalDistance = totalDistance;
        }

        /**
         * 获取旅行路径
         *
         * @return 城市列表
         */
        public List<City> getPath() {
            return path;
        }

        /**
         * 获取总距离
         *
         * @return 总距离
         */
        public double getTotalDistance() {
            return totalDistance;
        }
    }
} 